Talk:Busy beaver function
Archive 1 It seems that overall the term "busy beaver function" is more popular. Should we consider moving this page? -- ve 19:23, September 5, 2015 (UTC) Should we rename the article to "Busy beaver function"? Yes No Weird alternative for S(n) Define s(n,c) to be maximum shifts function for finite tape limited to c cells. If this finite-tape TM's head escapes cells, it halts. Is g(n) = s(n,n) uncomputable? And can s(n,c) from some c be uncomputable? Ikosarakt1 (talk ^ ) 05:18, September 19, 2015 (UTC) : There are only finitely many (exponentially many) possible tape configurations, so we know that the machine doesn't halt iff it repeats a configuration. We can check if this happens by simply keeping track of all configurations the machine reaches and looking for repetition. Hence we can decide whether these machines halt, which makes s(n,c) computable. Indeed, this function is upper bounded by number of possible configurations which, I believe, is \(2^c\cdot c\cdot n\) (each of c cells can take 2 values, there are c possible head positions and n possible states) : By the way, this is closely related to . LittlePeng9 (talk) 06:50, September 19, 2015 (UTC) ::I was too slow and had a conflicting edit saying basically the same. A few things to add: your machine (I'll call it a Deterministic Bounded Automaton) can be thought of as a Turing machine where the input tape has the symbols [], symbolizing the left and right ends of the tape. For a TM to be an DBA, the TM's rules must restrict it from escaping or overwriting the end markers. Also, the input must be wrapped in these markers and [ has to be immediately to the left of the TM starting position. ::LittlePeng9 gave an upper bound and a computability proof, but didn't comment on how easy it is to compute. The DBA halting problem is primitive recursive (since the simulation time is bounded), and so is \(s(n,c)\). -- ve 07:20, September 19, 2015 (UTC) Fun fact BB(n) mod TREE(n) isn't computable function, but TREE(n) mod BB(n) is. Ikosarakt1 (talk ^ ) 04:01, September 23, 2015 (UTC) Can you prove the first statement? For what I know, it is possible that for all n large enough BB(n) is divisible by TREE(n). LittlePeng9 (talk) 04:54, September 23, 2015 (UTC) Which proof theory should I use? Ikosarakt1 (talk ^ ) 12:11, September 23, 2015 (UTC) : I suppose you are asking which axiomatic system to use. I would say that ZFC will be fine. LittlePeng9 (talk) 13:22, September 23, 2015 (UTC) : Sorry, I can make proof only in ZFC+"BB(n) mod TREE(n) is uncomputable". So yes, it's just a fun hypothesis. Ikosarakt1 (talk ^ ) 03:49, September 24, 2015 (UTC) :: What if the theory you described is inconsistent? -- ve 13:04, September 24, 2015 (UTC) ::It would mean that BB(n) mod TREE(n) is computable. Ikosarakt1 (talk ^ ) 14:24, September 24, 2015 (UTC) :::I think vell's point is that in this case your proof would be unsound, so that you would prove something that's not true. :::(it's also possible that this theory is inconsistent because ZFC is, but that's beyond the point) LittlePeng9 (talk) 14:30, September 24, 2015 (UTC) Shocking thoughts I've heard about universal Turing machines which can simulate others. But that makes BB(n) even more crazy. Imagine, say, 100-state TM (A) which can simulate another, billion-state TM (B) which returns insane number of 1's (corresponding to its recursive level). Or even worse, TM (B) may simulate some TM © with even more states. In that case, I think even BB(100) is hopeless to be beaten by explicitly defined recursive function (not even saying about proving its value). 19:53, October 25, 2015 (UTC) :Universal turing machines (those that simulate others) don't work exactly like that. They never halt, and are built such that they eventually simulate all possible turing machines. If a turing machine could simulate a turing machine with a greater number of states (and an equal/greater amount of colors) than the function would clearly be ill defined. For example, we'd have BB(100) equal at least BB(10^6), which would be equal to at least BB(10^12), which would be equal to at least BB(10^25), which would be equal to... and so forth till literally infinity. Direct simulation of turing machines with smaller amount of states is possible though (and with 2 tapes it's not even very hard), and you can see an example of that on my blog post here. Maybe called Googology Noob (talk) 11:07, January 22, 2016 (UTC) ::Actually, a Turing machine (A) with \(n\) states can simulate a machine (B) with \(m>n\) states. But here is the catch: (A) must operate with a specific input, not just empty input. An example is this machine of mine, which in principle can simulate a binary Turing machine with arbitrary number of states (the machine itself isn't binary, but there are standard ways of turning it into a binary TM). This doesn't make BB ill-defined, because we need to encode whole machine (B) into a string which would be a prefix to the input. LittlePeng9 (talk) 12:40, January 22, 2016 (UTC) :::In theory, you can have turing machines that can simulate any other turing machine given the right input. The problem is, with the small ones, the input is infinitely wide, and even with larger ones, having the machine that would write the input for the universal machine would usually take at least as many states as the original turing machine does. Tomtom2357 (talk) 08:55, January 25, 2016 (UTC) ::::LittlePeng9: That sounds interesting, but your link directs to the binary palindrome checker. Maybe called Googology Noob (talk) 15:08, January 30, 2016 (UTC) New Bounds I believe I have shown some new bounds of the Busy Beaver function using an accelerated FGH (f_0(n)=n+1, f_a+1(n)=f_an+2(n+2), f_a(n)=f_an+2(n+1)) here, mainly that \(\Sigma\)(25)>f_w2(3) and that \(\Sigma\)(27)>~f_w^2(12) (though obviously more bounds can be made on that). Can I put those bounds here? Maybe called Googology Noob (talk) 07:16, January 9, 2016 (UTC) : Your bound isn't a bound for \(\Sigma(27)\), but rather \(\Sigma(27,6)\), which is a multi-color variant of BB function (the symbols used are _,1,w,W,i,|,l , did I miss anything by a chance?). Although this is some bound, I honestly don't think it's of enough relevance to put it on this page - we tend to put multi-color bounds only if they beat some "milestone" in FGH. LittlePeng9 (talk) 08:05, January 9, 2016 (UTC) :: It uses all of those symbols, but not every symbol is used by each state (Obviously such a bound for \(\Sigma(27,6)\) would not be much). Each state uses exactly 2 colors. Maybe called Googology Noob (talk) 12:39, January 9, 2016 (UTC) :::That doesn't matter - for \(\Sigma (m,n)\) you can use no more than \(n\) colors in total. Deedlit11 (talk) 23:20, January 9, 2016 (UTC) ::::Oh, OK. Somehow I didn't realize that. Maybe called Googology Noob (talk) 06:07, January 10, 2016 (UTC) Other numbers estimated using BB(n)? I think for computable numbers the Busy Beaver function would be a good way to possibly envision their size. I know that BB(18) is greater than Graham's Number, and I heard that Loader's Number is somewhere around BB(160), but what abuot the following? - Zootzootplex - TREE(3) - SGC(13) - Tetrathoth - Gongulus - The various Fish numbers (aside from 4 and 7) - Kungulus - Meameamealokkapoowa oompa Does anyone have any estimates? —Preceding unsigned comment added by 148.75.113.243 (talk • ) 10:12, September 6, 2016 (UTC) :There's no way it was proven that Loader's number is somewhere around BB(160). What they meant was probably that some number around 160 is the smallest number such that some people figured out a proof that it's larger than Loader's number. It can be proven from the Church Turing thesis that if for each positive integer n'', you will eventually state a lower bound for ''BB(n'') and only do it once, then for some ''t, BB(n'') is larger than the lower bound for it that you will state for all ''n > t''. The same goes for the frantic frog function ''S(n''). There probably exists a 6 state 2 color turing machine that can some people have the resources to prove doesn't halt after TREE(3) steps but hasn't been proven to eventually halt and it can probably be proven that there's no proof in some very high level proof system that it never halts. If it does eventually halt, then ''S(6) is a whole lot larger than it's current proven lower bound. Although we probably don't have the resources to think of a mathematical proof of it, it can probably be proven from the Church Turing thesis that that turing machine doesn't even halt after a number of steps equal to Loader's number. Blackbombchu (talk) 18:40, September 6, 2016 (UTC) :1. Zootzootplex—Preceding unsigned comment added by 148.75.113.243 (talk • ) 12:34, September 7, 2016‎ (UTC) :::About TREE(3) and SCG(13): The thousand part is talking about bounds that are actually feasible to prove, while "12 to 50" means what we guess where the actual value falls in. :::About kungulus: in one interpretation (which seems to be advocated by Bowers himself), kungulus' growth rate is aroung \(\Gamma_0\) (the Feferman–Schutte ordinal), which is smaller than the Bachmann-Howard ordinal. There is a bound for Bachmann-Howard ordinal using 81 states and 10 colors, which is around a few hundred states and 2 colors using the color reduction technique. I still won't comment on meameamealokkapoowa oompa though, since one definition puts it in an incredibly high growth rate that I can't understand it. -- ☁ I want more ⛅ 13:53, September 7, 2016 (UTC) Rayo's number How many states do we need to beat Rayo's number? Googol, Googolplex or Loader's number? -- 17:52, September 7, 2016 (UTC) :Since Rayo's number is bigger than Sigma(), there is no way to result it. AarexWikia04 - 19:55, September 7, 2016 (UTC) :Rayo's number: This needs extremely many states, something that is not really much smaller than Rayo's number. :Googol: 6 is enough, 5 is conjectured to be not enough. :Googolplex: 7 is enough and I would personally conjecture 6 to be enough as well. :Loader's number: It is not known, but probably 1,000 states is sufficient. :Wythagoras (talk) 14:27, September 9, 2016 (UTC) \(\Sigma\) might be faster than we suspect I call Turing machine ™ "semi-universal" if it can simulate some other TM (particularly with larger number of states) with some input. Now imagine if there is 10-state TM which simulates some 1000-state TM which computes some fast-growing recursive function with sufficiently large input. What if \(\Sigma(10)\) is already larger that anything what we defined so far using computable function? Moreover, there might be "chains" of simulations: that 1000-state TM might be itself a simulator, for, say, \(10^{100}\)-state TM! (o_O) 05:13, November 14, 2016 (UTC) :Indeed. Just because we could build TM of some power with a bunch of states, it doesn't mean we can claim it isnt beat by a much lower numbered BB champion. Chronolegends (talk) 05:25, November 14, 2016 (UTC) :Although this is possible, it is rather unlikely that this approach will lead us to a new lower bounds on BB numbers. The reason for why I think so is that, in order for this to be feasible, the additional input allowing the 10-state TM to simulate the 1000-state TM would have to be relatively short, which would mean that, whatever the 1000-state TM was to do, it was terribly wasteful at it, given that a machine with so many states fewer was able to do the same job. In practice, if this were done, one would probably that the 1000-state TM was a less efficient version of the 10-state TM, rather than that the 10-state TM is a more efficient version of 1000-state TM. So all in all, I just think "semi-universal" TMs are plain unfeasible. :As for the remark about \(\Sigma(10)\) - heck, we don't even know this about \(\Sigma(5)\)! As unlikely as it seems, it might be the case that one of the unresolved 5-state TMs produces output vastly larger than any known computable notation. LittlePeng9 (talk) 09:29, November 14, 2016 (UTC) By the way, there is an idea about how to improve our current bounds for \(\Sigma(n)\). One can pick some UTM, like this. Then waste some states to write input correspondent to some known powerful TM, like this. 07:58, November 14, 2016 (UTC) :First, let me point out that using Wolfram's (2,3) TM would be probably the worst idea to simulate another TM one can think of. There are a few reasons for that, among them the fact that this TM needs an infinite, nonrepeating input and the fact that it never halts. To be honest, I don't even know under what measure this machine is universal (and it seems community doesn't know either...). :There are some proper UTMs which could be actually used for this purpose there are small 2-symbol UTMs (there is one with 19 states, there is also one with 18 states, but it lacks a halting instruction too). However, these UTMs require input of considerable size, which would take a long time to produce (we'd have to waste a lot of states), causing us to spend more states than the original machine had (using Baiocchi's machine and the hydra machine you've linked we'd probably only get a lower bound for \(\Sigma(n)\) for \(n\) on the order of thousands if not tens of thousands. :On a positive side though, such UTMs can be used for less specific bounds, for example to prove that \(\Sigma(n)\) outgrows any computable function. There are easier ways to do this as well, but still :) LittlePeng9 (talk) 09:29, November 14, 2016 (UTC) ::Wait what, this must be fastest! AarexWikia04 - 12:33, November 14, 2016 (UTC) :::What must be fastest? LittlePeng9 (talk) 13:04, November 14, 2016 (UTC) Basic BB question Why does a 2 state busy beaver produce more 1s than a 1 state busy beaver? What is the difference between a 1 state and 2 state busy beaver? :Do you know the definition of a Turing machine? Do you know what's the difference between 1-state and 2-state Turing machine? LittlePeng9 (talk) 08:13, November 18, 2016 (UTC) BB(n) and ordinal Does anyone know which BB(n) has the large veblen ordinal? :What does it mean that a number has an ordinal? LittlePeng9 (talk) 09:34, November 19, 2016 (UTC) So the Busy Beaver function doesn't use recursion levels? So the turing machine states are not ordinals or recursion levels? :Correct. LittlePeng9 (talk) 18:15, November 19, 2016 (UTC) Golapulus Does anyone know which BB(n) is larger than Golapulus? :You mean one of these Bowers' numbers which aren't well-defined? Your question is hard to answer, because golapulus is, well, not well-defined. LittlePeng9 (talk) 19:45, November 20, 2016 (UTC) Okay. I suppose that n = 100 is enough, but it might be even smaller. 20:38, November 20, 2016 (UTC) How does the Xi function go beyond the Busy Beaver function? :Did you read the article on Xi function before asking that? it has the answer you are looking for in part 1.2 "SKIΩ calculus'" Chronolegends (talk) 08:11, November 22, 2016 (UTC) ' :SKI calculus is essentially equivalent in strength to Turing machines, so we expect the xi function without Ω combinator to be, in a way, comparable to BB function. But then adding Ω combinator makes SKIΩ calculus stronger than TMs, so xi function is stronger than BB. LittlePeng9 (talk) 08:27, November 22, 2016 (UTC) Two questions Does anyone know how many possible 100-state Turing machines there are? How is it a proven fact that BB(18) is larger than Graham's number? :First question: please make sure you have read the whole article before asking such a question. Second question: a machine has been constructed which achieves an output larger than Graham's number with 18 states. LittlePeng9 (talk) 20:46, November 23, 2016 (UTC) The game What is the difference between the Busy Beaver function and the Busy Beaver Game? :The busy beaver game is the problem of finding the values of the busy beaver function. LittlePeng9 (talk) 17:10, November 25, 2016 (UTC) ::Okay. Thanks. Why is it so strong? What is the main reason the busy beaver function is uncomputable? Is it because busy beavers are turing machines themselves? :uncomputable just means there is no algorithm that can compute it :Chronolegends (talk) 01:27, November 26, 2016 (UTC) :The main reason is the following idea: whatever computable function \(f(n)\) you choose (assume its increasing for simplicity), there is a Turing machine M which computes it. By adding a few states we can create a machine M' (with, say, \(C\) states) which computes \(f(2n)\). From there you construct, for each \(k\), a machine M'k with k more states which computes \(f(2k)\) from the empty input, so \(BB(C+k)\geq f(2k)\). For large \(k\) this gives \(BB(C+k)\geq f(2k)>f(C+k)\). :Recap of the idea: for any computable function, we can create amachine computing a faster growing function and use it to give lower bounds for busy beaver. LittlePeng9 (talk) 09:21, November 26, 2016 (UTC) Okay. Cool. How does the Busy Beaver function relate to first-order logic? What are axioms for the Busy Beaver function? :There is no such thing as axioms for the BB function as far as I know. There is also no direct relation between BB function and first-order logic, but BB is expressible in some first order logics, like first-order arithmetic or FOST. LittlePeng9 (talk) 18:52, November 26, 2016 (UTC) Oracle TMs Does a n-state oracle turing machine output more 1s than a n-state regular turing machine? :Depends on an oracle and the TM - there are n-state oracle TMs which output no 1s, which is less than what some regular TMs output. But I suppose the question is more about oracle busy beaver vs regular busy beaver, in which case the answer is yes, at least for most oracles. The precise answer probably depends on the oracle and on how precisely oracle calls are implemented, but with, for example, a halting problem oracle, the corresponding oracle BB definitely outgrows the regular BB. LittlePeng9 (talk) 18:05, November 28, 2016 (UTC) Section break What is the difference between BB(n), BB(k), and BB(2k)? :What is the difference between n''2, ''k''2, and (2''k)2? -- ve 02:21, December 2, 2016 (UTC) Is a N-state the same as a program? What is the difference between a N-state and a function? I know the Busy Beaver function is uncomputable, but if you were to try to compute the Busy Beaver function; how would the input look like? :"N-state" is a property of a Turing machine; every Turing machine uses a certain number of states, and the more that you can use, the more complicated your machine can be and the larger the class of functions you can compute. :It looks like you need to learn how a works; the Wikipedia page is a good start. There are many examples of Turing machines at http://googology.wikia.com/wiki/User:Vel!/Turing_golf. To compute BB(n), the idea is to try to program a machine that outputs as many 1's as possible when you start with a tape consisting of all 0's, and you have n states available. Deedlit11 (talk) 22:28, December 2, 2016 (UTC) Does an oracle Turing machine go beyond BB(BB(BB(...n times...BB(BB(BB(n)))? In other words does a N-state oracle Turing machine output more 1s than the Busy Beaver function (N-state regular Turing machines) outputs being iterated into itself multiple times? :It depends on the oracle being used. The obvious next step after regular TMs is to add an oracle for either the Halting function or the Busy Beaver. (It doesn't much matter which since you can compute one from the other.) We can call these machines TM2 machines, and then define BB2(n) to be the largest number of ones outputted by a TM2 machine with at most n states, starting from a tape of all zeroes. :Just as the BB(n) function will beat out any function computable by a normal algorithm, the BB2(n) function will beat out any function computable by a algorithm where you are allowed to call the BB(n) function. Since "apply the BB function n times starting from n" is a valid algorithm, BB2(n) will eventually dominate BBn(n). You can of course go further, creating a long ordinal hierarchy starting from BB(n), and the result will still be computable from BB(n), and therefore beaten by BB2(n). :By the way, please sign your posts, so the rest of us don't have to. Deedlit11 (talk) 09:17, December 3, 2016 (UTC) How many more 1s would a 3-state oracle Turing machine output than a 3-state regular Turing machine? How do i sign my posts? I don't know how to do that. :It depends on the precise implementation of an oracle machine (and of course the oracle being used). Unfortunately, while there is a more or less standard implementation of the normal Turing machine (not universal, but the first few Busy Beaver numbers have been calculated for it so it's what we go with), there is no standard implementation for a machine with an oracle for the Halting function or Busy Beaver function. I can say a couple of things though: I imagine you will get higher numbers for oracle machines with the Busy Beaver function than with the Halting function, simply because it is an immediate fast-growing function. Another thing to worry about is how strictly defined the input parameters are for the oracle call. For example, if you require that to input n into the oracle, you must have a contiguous string of n 1's with the head at the leftmost 1, than with say two free states I don't know if you could input a number greater than n=2. On the other hand, if you don't require that the head be at the leftmost position of the string of 1's, then one can create a string of four 1's with two free states, so we could then make an oracle call and return BB(4) = 13. So it all depends. :To sign your posts, simply put four ~'s at the end of your post. Deedlit11 (talk) 00:43, December 6, 2016 (UTC) What are inputs for the Busy Beaver function? How does an oracle Turing machine output more 1s by solving the halting problem? What is the difference between Turing machines that are Busy beavers and Turing machines that are not Busy beavers? 00:14, December 15, 2016 (UTC) :Turing machines come with a tape, so whatever is written on the tape when the Turing machine starts running is the "input" for the Turing machine. When there is more than one tape, usually one will be labelled the "input tape". :If you have an oracle for the halting problem, then you can compute the Busy Beaver function. Given an input n, just search through all Turing machines with n states and check whether they halt or not. For the TMs that halt, run them through to completion, and count the number of steps or symbols printed. Keep track of the maximum score. After you have run through all possible Turing machines, you will have the Busy Beaver number. :Since you can compute BB(n), you can also compute BB(BB(n)), or BB^n(n), or BB^(BB(n))(n), or much faster growing functions starting from BB(n). So the BB function for Turing machines with an oracle for the halting problem grows very much faster than the normal BB unction. :A Busy Beaver Turing machine is simply a Turing machine that prints the most 1's. Deedlit11 (talk) 02:18, December 15, 2016 (UTC) Okay. Thanks for the information. If Turing machine levels w+w are possible (nth-order turing machines, like oracle turing machines are 2nd-order turing machines) then are TMLVO (Large Veblen Ordinal-order turing machines) possible? Like TMw+w. 03:25, December 15, 2016 (UTC) :Yes. You can have an \(\alpha\)th level Turing machine for any \(\alpha\) that you construct an ordinal notation for, so you can go beyond \(\omega_1^{\text{CK}}\). Deedlit11 (talk) 08:57, December 15, 2016 (UTC) Are Turing machine states inserted or attached to Turing machines or are they built into Turing machines? Let's say for example, a 3-state Turing machine. Is the 3-state inserted into the Turing machine, so that the Turing machine can operate or is the 3-state already built into the Turing machine? 21:50, December 15, 2016 (UTC) :A Turing machine is an abstract computing machine, and states are part of it. Really, you should read the Wikipedia entry , and possibly google other intros to get an understanding. Deedlit11 (talk) 01:14, December 16, 2016 (UTC) Could Turing machines compute Hypcos's R function and Harvey Friedman's TREE sequence? 12:58, December 19, 2016 (UTC) :Those are both computable functions, so yes. Deedlit11 (talk) 01:05, December 20, 2016 (UTC) How do you simulate a Turing machine? 15:04, December 22, 2016 (UTC)